#! /usr/bin/env python

import math
import os.path

primeList = []

def __init__():
    global primeList
    if os.path.exists('prime'):
        primeList = []
        for line in open('prime'):
            for k in line.replace('\n','').split(' '):
                primeList.append(int(k))
    else:
        primeList = [2]
        for i in range(3,1000000):
            if isPrime(i):
                primeList.append(i)

def isPrime(i):
    '''return True if i is a prime
    isPrime(1) return False
    '''
    global primeList
    if i==1:return False
    if i==2:return True
    j = math.sqrt(i)
    for k in primeList:
        if i%k==0:
            return False
        if k>j:
            return True
    print r'i cann\'t handle prime number excceed ' + primeList[-1]
    1/0

def properDivisorOf(n):
    '''return a list of all factor of n'''
    half = n/2
    return [i for i in range(1,n/2+1) if n%i==0]

def primeFactorOf(n):
    '''return a list of all prime factor of n'''
    q = int(n/2)
    k = 0
    l = []
    while primeList[k] <= q:
        if n%primeList[k] == 0:
            l.append(primeList[k])
        k += 1
    if not l:
        #prime
        l.append(n)
    return l
    
    

def comb(items, n=None):
    '''generate the combination of items
    items: a list from which we fetch elements
    n: the length of item we want, if omitted n is length of items
    
    example: comb([1,2,3],2) will generate
    [1, 2], [1, 3], [2, 3]'''
    if n is None:
        n = len(items)    
    for i in range(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[i+1:]
            for c in comb(rest, n-1):
                yield v + c

def perm(items, n=None):
    '''generate the permutations of items
    items: a list from which we fetch elements
    n: the length of item we want, if omitted n is length of items
    
    example: perm([1,2,3],2) will generate
    [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]'''
    if n is None:
        n = len(items)
    for i in range(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[:i] + items[i+1:]
            for p in perm(rest, n-1):
                yield v + p
                

def fact(n):
    '''return the factorial of n'''
    return reduce(lambda x,y:x*y,range(1,n+1),1)

__init__()

